// @algorithm @lc id=1866 lang=cpp 
// @title restore-the-array-from-adjacent-pairs


// #define print(...)
// @test([[2,1],[3,4],[3,2]])=[1,2,3,4]
// @test([[4,-2],[1,4],[-3,1]])=[-2,4,1,-3]
// @test([[100000,-100000]])=[100000,-100000]
using iterator = vector<vector<int>>::iterator;
class Solution {
public:
    vector<int> restoreArray(vector<vector<int>>& adjacentPairs){
        print("\npairs=", adjacentPairs, "\n")
        size_t n = adjacentPairs.size();
        unordered_map<int, vector<int>> adjs;
        for(auto & a : adjacentPairs){
            adjs[a[0]].push_back(a[1]);
            adjs[a[1]].push_back(a[0]);
        }
        print("adjs=", adjs, "\n")
        vector<int> ans;
        for(auto & [a,d] : adjs)
            if(d.size()==1){
                ans.push_back(a);
                ans.push_back(d[0]);
                break;
            }
        while(ans.size() < n+1){
            for(auto & d : adjs[*ans.rbegin()]){
                if(*(ans.rbegin()+1) != d){
                    ans.push_back(d);
                    break;
                }
            }
        }
        print("ans=", ans, "\n")
        return ans;
    }
};